In recent years, group signature technology has been proposed in the fields of cryptography and signature studies.
Meanwhile, other technology has been proposed for the design of electronic circuits specializing in specific calculations, wherein the circuit behavior is specified in a high-level language such as c, and then behavioral synthesis is conducted to output a configuration of the electronic circuit. In other words, due to advances in computer technology, it is becoming typical to design, analyze, and evaluate semiconductor integrated circuits by using CAD (computer-aided design) systems provided with a behavioral synthesizer and a logic synthesizer.
For example, a circuit design support system provided with a behavioral synthesizer and a logic synthesizer has been disclosed in Unexamined Japanese Application KOKAI Publication No. 2007-272671.
When designing a semiconductor integrated circuit with the use of a circuit design support system, the designer first prepares a behavioral level description, including input ports, bit-widths of variables, and other information used for H/W conversion.
Next, the designer uses a behavioral synthesizer to convert the behavioral level description into an RTL (register transfer level) description wherein the logic to be realized is expressed as logical functions between registers.
Subsequently, the designer uses a logic synthesizer to convert the RTL description into a gate level logic circuit.
In such a circuit design methodology, it is typical to make the electronic circuit layout multi-layered and increase the bandwidth for information exchange, thereby enabling faster operation (as disclosed in “Multi-layer AHB Overview”, ARM DVI 0045B, ARM, 2001, 2004)
Meanwhile, a basic algorithm for generating and verifying group signatures has also been disclosed (see Isamu Teranishi, “A New Group Signature Scheme Secure Under Improved Definitions with a Fix to Previous Schemes”, IEICE, ISEC 2004, 2005).
The group signature herein is subject to: a predetermined bit-length K[n]; a predetermined bit-length K[l]; a predetermined bit-length K[e]; a predetermined bit-length K[e′]; a bit-length K[q] of a prime number q denoting the order of a finite group GG defined by an elliptic curve; an output bit-length K[c] returned by a hash function Hash applied to a bit sequence of arbitrary length; a bit-length K[S] such that when a random number r of bit-length |a|+K[S] for any integer a is selected, then a+r and a are statistically indistinguishable; security parameters K=(K[n], K[l], K[e], K[e′], K[q], K[c], K[S]); an integer λ=K[n]+K[q]+K[S]; a set of integer values Λ in a range from 0 (inclusive) to 2λ (exclusive); scalar multiplication [c](·) on the elliptic curve; point addition +e on the elliptic curve; and point subtraction −e on the elliptic curve.
The Issuer's key pair for the group signature is
ipk=(n, a[0], a[1], a[2]);
isk=(p[1], p[2])
where p[1] and p[2] are safe prime numbers of bit-length K[n]/2; n=p[1]p[2]; and a[0], a[1], and a[2] are elements of the cyclic subgroup QR(n) with respect to n.
In addition, the Opener's key pair for the group signature is
opk=(q, G, H[1], H[2]);
osk=(y[1], y[2])
where y[1] and y[2] are elements of the prime number q-modulo finite field Zq, G is an element of the finite group GG, H[1]=[y[1]]G, and H[2]=[y[2]]G.
Meanwhile, the User-Revocation manager's key pair for the group signature is
rpk=(l, b, w);
rsk=(l[1], l[2])
where l[1] and l[2] are safe prime numbers of bit-length K[l]/2; l=l[1]l[2]; and b and w are elements of the cyclic subgroup QR(l) with respect to l.
In addition, the i-th user's key pair for the group signature is
msk[i]=x[i];
mpk[i]=(h[i], A[i], e′[i], B[i])
where x[i] is an element of the set Λ; and A[i], B[i], e′[i], and h[i] satisfy h[i]=[x[i]]G, B[i]=bl/e′[i] (mod l), e[i]=2K[e]+e′[i], and a[0]a[1]x[i]≡A[i]e[i] (mod n).
When generating a signature for a message m from the i-th user, the following are first chosen randomly: an element ρ[E] of the finite field Zq, a bit sequence ρ[m] of bit-length K[n]/2, a bit sequence ρ[r] of bit-length K[l]/2, a bit sequence μ[x] of bit-length λ+K[c]+K[S], a bit sequence μ[s] of bit-length K[e]+K[n]/2+K[c]+K[S], a bit sequence μ[e′] of bit-length K[e′]+K[c]+K[S], a bit sequence μ[t] of bit-length K[e′]+K[l]/2+K[c]+K[S], and an element μ[E] of the finite field Zq.
Next, E[0]=[ρ[E]]G, E[1]=h[i]+e[ρ[E]]H[1], E[2]=h[i]+e[ρ[E]]H[2], E=(E[0], E[1], E[2]), and V[ComCipher]=([μ[E]]G, [μ[x]]G+e[μ[E]]H[1], [μ[x]]G+e[μ[E]]H[2]) are computed.
In addition, A[COM]=A[i]a[2]ρ[m] (mod n), B[COM]=B[i]wρ[r] (mod l), V[ComMPK]=a[1]μ[x]a[2]μ[s]A[COM]−μ[e′] (mod n), and V[ComREV]=wμ[t]B[COM]−μ[e′] (mod l) are computed.
Subsequently, c=Hash(K, ipk, opk, rpk, E, A[COM], B[COM], V[ComCipher], V[ComMPK], V[ComRev], m) is computed.
Next, τ[x]=c x[i]+μ[x] (mod q), τ[s]=c e[i]ρ[m]+μ[s] (mod q), τ[t]=c e′[i] ρ[r]+μ[t] (mod q), τ[e′]=c e′[i]+μ[e′] (mod q), and τ[E]=cρ[E]+μ[E] (mod q) are computed.
Lastly, the signature (E, A[COM], B[COM], c, τ[x], τ[s], τ[t], τ[e′], τ[E]) is output.
On the other hand, when verifying a signature σ=(E, A[COM], B[COM], c, τ[x], τ[s], τ[t], τ[e′], τ[E]) attached to the message m (where E=E[0], E[1], E[2]), the following is first computed: V′[ComCipher]=([τ[E]]G−e[c]E[0], [τ[x]]G+e[τ[E]]H[1], [τ[x]]G+e[τ[E]]H[2]−e[c]E[2]).
Next, p=c 2K[2]+τ[e′], V′[ComMPK]=a[0]ca[1]τ[x]a[2]τ[s]A[COM]−p (mod n), and V′[ComREV]=bcwτ[t]B[COM]−τ[e′] (mod l) are computed.
In addition, c′=Hash(K, ipk, opk, rpk, E, A[COM], B[COM], V′[ComCipher], V′[ComMPK], V′[ComREV], m) is computed.
Subsequently, if all of |τ[x]|≦λ+K[c]+K[S], |τ[e′]|≦K[e′]+K[c]+K[S], and c′=c hold, then verification succeeds. Otherwise, verification fails.
There is strong demand for a signature generation apparatus and a signature verification apparatus able to execute processing for computing group signatures at high speeds using an electronic circuit.
At the same time, since electronic circuits designed in a multi-layered manner are generally increasing in cost, it is preferable to realize a circuit configuration whereby manufacturing costs can be curtailed while still enabling increased speeds.